In an internal combustion engine, usually if an engine starts to be decelerated in operation, the supply of fuel to the inside of the combustion chambers is stopped. When the engine speed next falls to a preset speed, the supply of fuel is restarted. In this case, if an exhaust purification catalyst is arranged inside the engine exhaust passage, when the supply of fuel is stopped, a large amount of oxygen will be supplied to the exhaust purification catalyst. If a large amount of oxygen is supplied to the exhaust purification catalyst in this way, the HC (hydrocarbons) or CO (carbon monoxide) which had been deposited on the exhaust purification catalyst before the supply of fuel was stopped will react with the oxygen. Due to the heat of oxidation reaction at that time, the temperature of the exhaust purification catalyst will rise. Further, at the time of restart of the supply of fuel, the oxygen which had been deposited on the exhaust purification catalyst while the supply of fuel was stopped will react with the HC or CO in the exhaust gas, and the temperature of the exhaust purification catalyst will also rise due to the heat of oxidation reaction at that time. Therefore, known in the art is a catalyst temperature estimating device designed to consider the heat of these oxidation reactions and estimate the temperature of the exhaust purification catalyst after restart of supply of fuel (for example, see Japanese Patent Publication No. 2007-309244A).